Date: Tuesday, 26-Nov-96 00:09:46 GMT
Server: NCSA/1.3
MIME-version: 1.0
Content-type: text/html
Last-modified: Wednesday, 20-Sep-95 22:45:59 GMT
Content-length: 2987

<Title> NSF CAREER Project</Title>

<!WA0><IMG ALIGN = middle SRC = http://www.cse.nd.edu/graphics/NDCSE.gif
ALT = "[ U_N_I_V_E_R_S_I_T_Y___o_f___N_O_T_R_E___D_A_M_E ]">

<H1> <!WA1><img align=bottom src=http://www.cse.nd.edu/faculty/sha.gif> 
Principal Investigator: <!WA2><A HREF = "http://www.nd.edu/~esha/index.html"> Dr. Edwin Sha </a> </h1>

<H1> NSF CAREER Award (1995 -  1998) </h1>

<h2> Grant Number: MIP-9501006 </h2>

<H2> Title: High-Level Design Methodologies for Time-Optimal and Memory-Optimal
Systems </H2>

 <H3> Abstract: </h3>
<p>
 Since most time and memory critical parts of scientific computing
applications are usually concentrated in 
nested loops, this research focuses on optimization 
algorithms for synthesis of those multi-level loops.
The loop nests are modeled as Multi-dimensional Data-Flow
Graphs (MDFG), and algorithms taking advantage of the 
multi-dimensionality are designed.
Computation of a nested loop can be visualized as the
repeated executions of the iteration body in a multi-dimensional
iteration space.
By considering the iteration space and the iteration body simultaneously,
the proposed transformation and optimization
techniques will be able to optimize throughput and memory requirement
at the behavior level.
The proposed project will develop polynomial-time algorithms 
on various graph models rather than using traditional integer linear programming
approaches.
Research topics of this project include:

<p>
1. Graph transformation and
optimization techniques using the concept of multi-dimensional
interleaving and retiming
to obtain optimal throughput with the minimal increase of memory requirement.

<p>
2. Data scheduling techniques to 
minimize the size of the first-level memory (on-chip memory) 
for a given time constraint, 
and techniques to maximize data utilization for a given size of on-chip memory.

<p>
3. Design automation for Hardware/Multi-Software, HMS, 
(special hardware with multiple processors) co-design.

<p>
4. Development of synthesis tools for multi-dimensional applications.

<H2> Graduate Students </h2>
 <UL>
  <LI> <!WA3><A HREF = "http://www.nd.edu/~npassos"> Nelson Passos </A> (npassos@bach.helios.nd.edu)
  <LI> <!WA4><A HREF = "http://www.nd.edu/~msheliga"> Michael Sheliga</A> (msheliga@bach.helios.nd.edu)
  <LI> <!WA5><A HREF = "http://www.nd.edu/~dsurma"> David Surma </A> (dsurma@bach.helios.nd.edu)
  <LI> <!WA6><A HREF = "http://www.nd.edu/~cchantra"> Joy Chantana </A> (cchantra@bach.helios.nd.edu)
  <LI> <!WA7><A HREF = "http://www.nd.edu/~stongsim"> Dev Tongsima </A> (stongsim@bach.helios.nd.edu)
  <LI> <!WA8><A HREF = "http://www.nd.edu/~clang"> Chenhua Lang</A> (clang@bach.helios.nd.edu)
 </UL>

<p>
<!WA9><A HREF= "http://www.cse.nd.edu/tech_reports/">
Technical Reports </a>
may be found in the CSE departmental report
archives.

<p>
<address> <br>
Dr. Edwin Sha <br>
Department of Computer Science and Engineering <br>
University of Notre Dame, <br>
Notre Dame, IN 46556, USA. <p>
219 631-8803 (Office) <br>
219 631-9260 (FAX) <br>

</address>

<p>
<address><b>esha@bach.helios.nd.edu  or <br>
 hms@cse.nd.edu</b></address>
<p>
<i>Revised - May 13, 1995.</i>


